package class10;

import cn.hutool.core.util.ArrayUtil;

import java.util.*;

/**
 * https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/description/
 * 插入和删除随机元素O(1)时间的结构
 * 解题思路：
 * 1.与Code11_InsertDeleteRandom方法相似，但 index 用sets存储
 */
public class Code12_RandomizedCollection {
    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        System.out.println(set.insert(4));
        System.out.println(set.insert(3));
        System.out.println(set.insert(4));
        System.out.println(set.insert(2));
        System.out.println(set.insert(4));

        System.out.println(set.remove(3));
        System.out.println(set.remove(4));
        System.out.println(set.remove(4));
        System.out.println(set.remove(4));

//        System.out.println(set.insert(0));
//        System.out.println(set.remove(0));
//        System.out.println(set.insert(-1));
//        System.out.println(set.remove(0));
    }

    private static class RandomizedSet {
        public Map<Integer, Set<Integer>> map;
        public int[] arr;
        public int r;
        public final int MAX = 2 * 100000;

        public RandomizedSet() {
            map = new HashMap<>();
            arr = new int[MAX];
        }

        public boolean insert(int val) {
            arr[r] = val;
            Set<Integer> set = map.getOrDefault(val, new HashSet());
            set.add(r++);   // 将 index 存入 set 中
            map.put(val, set); // 将
            return set.size() == 1;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            Set<Integer> sets = map.get(val);
            Integer index = sets.toArray(new Integer[0])[0];
            if (index < r - 1) { // 如果删除的是小于r-1的，则需要调换位置
                arr[index] = arr[r - 1];
                Set<Integer> set = map.get(arr[index]);
                set.remove(r - 1);
                sets.remove(index);
                set.add(index);
            } else { // 否则直接删除
                sets.remove(index);
            }
            if (sets.size() == 0) {
                map.remove(val);
            }
            r--;
            return true;
        }

        public int getRandom() {
            return arr[(int) (Math.random() * r)];
        }

        @Override
        public String toString() {
            return ArrayUtil.toString(map);
        }
    }
}
